home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 1999 #2 / Amiga Plus CD - 1999 - No. 2.iso / System-Boost / Workbench / Archive / bzip2-0.1pl2 / ALGORITHMS next >
Text File  |  1998-11-08  |  2KB  |  48 lines
  1.  
  2. Bzip2 is not research work, in the sense that it doesn't present any
  3. new ideas.  Rather, it's an engineering exercise based on existing
  4. ideas.
  5.  
  6. Four documents describe essentially all the ideas behind bzip2:
  7.  
  8.    Michael Burrows and D. J. Wheeler:
  9.      "A block-sorting lossless data compression algorithm"
  10.       10th May 1994. 
  11.       Digital SRC Research Report 124.
  12.       ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.ps.gz
  13.  
  14.    Daniel S. Hirschberg and Debra A. LeLewer
  15.      "Efficient Decoding of Prefix Codes"
  16.       Communications of the ACM, April 1990, Vol 33, Number 4.
  17.       You might be able to get an electronic copy of this
  18.          from the ACM Digital Library.
  19.  
  20.    David J. Wheeler
  21.       Program bred3.c and accompanying document bred3.ps.
  22.       This contains the idea behind the multi-table Huffman
  23.       coding scheme.
  24.       ftp://ftp.cl.cam.ac.uk/pub/user/djw3/
  25.  
  26.    Jon L. Bentley and Robert Sedgewick
  27.      "Fast Algorithms for Sorting and Searching Strings"
  28.       Available from Sedgewick's web page,
  29.       www.cs.princeton.edu/~rs
  30.  
  31. The following paper gives valuable additional insights into the
  32. algorithm, but is not immediately the basis of any code
  33. used in bzip2.
  34.  
  35.    Peter Fenwick:
  36.       Block Sorting Text Compression
  37.       Proceedings of the 19th Australasian Computer Science Conference,
  38.         Melbourne, Australia.  Jan 31 - Feb 2, 1996.
  39.       ftp://ftp.cs.auckland.ac.nz/pub/peter-f/ACSC96paper.ps
  40.       
  41. All three are well written, and make fascinating reading.  If you want
  42. to modify bzip2 in any non-trivial way, I strongly suggest you obtain,
  43. read and understand these papers.
  44.  
  45. I am much indebted to the various authors for their help, support and
  46. advice.
  47.  
  48.